//给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a² + b² = c 。 
//
// 
//
// 示例 1： 
//
// 
//输入：c = 5
//输出：true
//解释：1 * 1 + 2 * 2 = 5
// 
//
// 示例 2： 
//
// 
//输入：c = 3
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 0 <= c <= 2³¹ - 1 
// 
//
// Related Topics 数学 双指针 二分查找 👍 470 👎 0


package LeetCode.editor.cn;


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author ldltd
 * @date 2024-11-04 08:59:08
 * @description 633.平方数之和
 
 */
 
public class SumOfSquareNumbers {
    public static void main(String[] args) {
    //测试代码
    SumOfSquareNumbers fun = new SumOfSquareNumbers();
    Solution solution= fun.new Solution();

    System.out.println(solution.judgeSquareSum((2<<30)-1));


    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean judgeSquareSum1(int c) {
        for (int a = 0; a * a <= c / 2; a++) {
            int b = (int) Math.sqrt(c - a * a);
            if (a * a + b * b == c) {
                return true;
            }
        }
        return false;
    }
    public boolean judgeSquareSum(int c) {
        int l=0,r=(int)Math.sqrt(c);
        while (l<=r){
            if(l*l==c-r*r) return true;
            if(l*l<c-r*r) l++;
            else r--;
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
